#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define punct pair<int,int>
#define x first
#define y second
#define INF 100000000
#define NMAX 50000
using namespace std;

FILE *f=fopen("dijkstra.in","r");
FILE *g=fopen("dijkstra.out","w");

int i,j,n,m,a,b,c,now,z,d[NMAX];

vector<punct>v[NMAX];
queue<int>Q;

int main()
{
    fscanf(f,"%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        fscanf(f,"%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
    for(i=2;i<=n;i++)
        d[i]=INF;
    Q.push(1);
    while(!Q.empty())
    {
        now=Q.front();
        z=v[now].size();
        for(i=0;i<z;i++)
            if(d[v[now][i].x]>d[now]+v[now][i].y)
            {
                d[v[now][i].x]=d[now]+v[now][i].y;
                Q.push(v[now][i].x);
            }
        Q.pop();
    }
    for(i=2;i<=n;i++)
        if(d[i]==INF)fprintf(g,"0 ");
        else fprintf(g,"%d ",d[i]);
    return 0;
}