#include <fstream>
#include <vector>
#define maxn 50000
#define inf 1<<30 //2 la 30:>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <int> muchii[maxn],cost[maxn];
int n,m;
int viz[maxn],dist[maxn];

void citire()
{
    f>>n>>m;
    int i;
    for(i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y;
        muchii[x].push_back(y);
        f>>c;
        cost[x].push_back(c);
    }
}

void dijkstra(int nod)
{
    int j, i,min=inf,poz;
    viz[nod]=1;

    for(i=1;i<=n;i++)
        dist[i]=inf;
    dist[nod]=0;

    for(i=0;i<=muchii[nod].size();i++)
      dist[muchii[nod][i]]=cost[nod][i];

    for(i=1;i<n;i++)
    {
       for(j=1;j<=n;j++)
         if(!viz[j] && dist[j]<min)
           min=dist[j], poz=j;

        viz[poz]=1;

        for(j=0;j<muchii[poz].size();j++)
          if(dist[muchii[poz][j]]>dist[min]+cost[poz][j])
                     dist[muchii[poz][j]]=dist[min]+cost[poz][j] ;
    }
}
int main()
{
    citire();
    dijkstra(1);
    for(int i=2;i<=n;i++)
       g<<dist[i]<<" ";
    return 0;
}