#include <fstream>
#include<queue>
#include<bitset>
#define NMAX 50005
#define oo 999999
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

int D[NMAX];
vector< pair<int,int> > V[NMAX];
vector< pair<int,int> >::iterator it;
bitset<NMAX> Uz;
int N,M,x,y,c,lg,i;

class cmp{
public :
    inline bool operator()(int x,int y ){return D[x]<D[y];}
};
priority_queue< int, vector< int >, cmp > Heap;

int main()
{
    in>>N>>M;
    while(M--)
    {
        in>>x>>y>>c;
        V[x].push_back(make_pair(y,c));
    }
    Heap.push(1);
    for(i=2;i<=N;i++)D[i]=oo;
    while(!Heap.empty())
    {
        x = Heap.top();
        Heap.pop();
        lg =V[x].size();
        Uz[x] = 0;
        for(it=V[x].begin();it<V[x].end();++it)
        {
            y = it->first;
            c = it->second;
            if(D[y]>D[x]+c)
            {
                D[y] = D[x] + c;
                if(Uz[y]==0)
                {
                    Heap.push(y);
                    Uz[y] = 1;
                }
            }
        }
    }
    for(i=2;i<=N;i++)
    out<<(D[i]<oo?D[i]:0)<<' ';
    return 0;
}