#include <cstdio>
#include <cstring>
#include <set>
#include <vector>
using namespace std;

#define pb push_back
#define mp make_pair
#define nmax 50100
#define inf 1000000000

FILE *f1=fopen("dijkstra.in","r"),*f2=fopen("dijkstra.out", "w");
int n, m, d[nmax];
vector<int> g[nmax], c[nmax];
set< pair<int, int> > t;

void dijkstra()
{
    int i, j, k, val, x;

    for(i = 2; i <= n; i++) d[i] = inf;
    t.insert( mp(0, 1) );

    while( t.size() > 0 )
    {
        val = (*t.begin()).first, x = (*t.begin()).second;
        t.erase(*t.begin());
        for(i = 0; i < g[x].size(); i++)
         if(d[ g[x][i] ] > val + c[x][i] )
            d[ g[x][i] ] = val + c[x][i], t.insert(mp(d[g[x][i]],g[x][i]));
    }
}

int main(void)
{
    int i, x, y, z;
    fscanf(f1,"%d%d",&n,&m);
    for(i = 1; i <= m; i++)
        fscanf(f1,"%d%d%d",&x,&y,&z), g[x].pb(y), c[x].pb(z);
    dijkstra();
    for(i = 2; i <= n; i++)
       if(d[i]==inf)fprintf(f2,"0 ");
       else fprintf(f2,"%d ",d[i]);

    return 0;
}