#include <fstream>
#include<queue>
#include<bitset>
#define NMAX 50001
#define oo 0x3f3f
using namespace std;

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

int D[NMAX];
vector<int> V[NMAX];
vector<int> C[NMAX];
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(y);
        C[x].push_back(c);
    }
    Heap.push(1);
    Uz[x]=0;
    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(i=0;i<lg;i++)
        {
            y = V[x][i];
            c = C[x][i];
            if(D[y]>D[x]+c)
            {
                D[y] = D[x] + c;
                if(!Uz[y])
                {
                    Heap.push(y);
                    Uz[y] = 1;
                }
            }
        }
    }
    for(i=2;i<=N;i++)
    out<<(D[i]<oo?D[i]:0)<<' ';
    return 0;
}