#include <fstream>
#include <iostream>
#include <queue>
#define nmax 50004
#define fin "dijkstra.in"
#define fou "dijkstra.out"
#define inf 0x7fffffff
using namespace std;
ifstream t1(fin);
ofstream t2(fou);
int n,m1;
vector< pair<int,int> > m[nmax];
int d[nmax];

class mycomparison
{
public:
    bool operator () ( int a,int b)
    {
        return d[a]>d[b];
    }
};
priority_queue<int,vector<int>,mycomparison> q;


int main()
{
    int nod;
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    t1>>n>>m1;
    int n1,n2,cst;
    for(;m1;m1--)
    {
        t1>>n1>>n2>>cst;
        m[n1].push_back(make_pair(n2,cst));
    }

    int i;
    for(i=1;i<=n;i++) d[i]=inf;
    d[1]=0;
    q.push(1);
    vector< pair<int,int> >::iterator it;
    while(!q.empty())
    {
        nod=q.top(); q.pop();
        for(it=m[nod].begin();it!=m[nod].end();it++)
            if(d[it->first]> d[nod]+ it->second)
            {
                d[it->first]=d[nod]+it->second;
                q.push(it->first);
            }
    }
    for(i=2;i<=n;i++) if(d[i]!=inf) printf("%d ",d[i]);
                               else printf("0 ");
    fclose(stdin);
    fclose(stdout);
    return 0;
}