#include<cstdio>
#include<vector>
#include<queue>
#define MAX_N 50000
#define oo 2000000000
using namespace std;

int Dist[MAX_N+1], n, m;
vector< pair<int, int> > G[MAX_N+1];

struct comp
{
    bool operator() (const int &X, const int &Y)
    {
        return (Dist[X] > Dist[Y]);
    }
};

priority_queue<int, vector<int>,comp> Q;

void Dijkstra(int x)
{
    int i, Node;
    for(i=1; i<=n; i++)
        Dist[i] = oo;
    Dist[x] = 0;
    Q.push(x);
    while(!Q.empty())
    {
        Node = Q.top();
        Q.pop();
        for(vector<pair<int, int> >::iterator it = G[Node].begin(); it != G[Node].end(); ++it)
        {
            if(Dist[(*it).first] > Dist[Node] + (*it).second)
            {
                Dist[(*it).first] = Dist[Node] + (*it).second;
                Q.push((*it).first);
            }
        }
    }
}

int main()
{
    int x, y, c, i;
    FILE *fin, *fout;
    fin = fopen("dijkstra.in","r");
    fout = fopen("dijkstra.out","w");
    fscanf(fin,"%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        fscanf(fin,"%d%d%d",&x,&y,&c);
        G[x].push_back(make_pair(y,c));
    }
    Dijkstra(1);
    for(i=2; i<=n; i++)
        if(Dist[i] != oo)
            fprintf(fout,"%d ",Dist[i]);
    else fprintf(fout,"0 ");
    fprintf(fout,"\n");
    fclose(fin);
    fclose(fout);
    return 0;
}