#include <cstdio>
#include <vector>
#include <queue>
#define nod pair<int,int>
#define pb push_back
#define NMax 50005
#define INF 10000

using namespace std;

struct compar {
    bool operator() (const nod &a, const nod&b)
    {
        return a.second>b.second;
    }
};
priority_queue<nod, vector<nod>, compar> Q;
vector<nod> G[NMax];
int D[NMax];
bool viz[NMax];
int i, j, N, M, v, u, w, l;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    scanf("%d %d ",&N,&M);

    for(i=1;i<=M;i++)
    {
        scanf("%d %d %d",&u,&v,&w);
        G[u].pb(nod(v,w));
    }
    for(i=2;i<=N;i++)
        D[i]=INF;
    D[1]=0;
    Q.push(nod(1,0));

    while(!Q.empty())
    {
        u=Q.top().first;
        Q.pop();
        if(!viz[u])
        {
            l=G[u].size();
            for(i=0; i<l; i++)
            {
                v=G[u][i].first;
                w=G[u][i].second;
                if(!viz[v]&&D[u]+w<D[v])
                {
                    D[v]=D[u]+w;
                    Q.push(nod(v,D[v]));
                }
            }
            viz[u]=1;
        }
    }
    for(i=2; i<=N; i++)
        printf("%d ",D[i]);
    return 0;
}