#include <fstream>
#include <queue>
#include <set>
#define INF 99999
using namespace std;

ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
vector<int> V[50000];
vector<int> C[50000];
int D[50000];
bool intrat[50000];
struct cmp{
    bool operator()(int a,int b){return D[a]<D[b];}
};
//multiset<int,cmp> H;
//multiset<int,cmp>::iterator it;
vector<int> H;
vector<int>::iterator it;
int main()
{
    int N,M,x,y,c,i;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y>>c;
        V[x].push_back(y);
        C[x].push_back(c);
    }
    for(i=2;i<=N;i++) D[i] = INF;
    //dijkstra
    H.push_back(1);
    make_heap( H.begin(), H.end(),cmp() );
    while(H.size())
    {
        it = H.begin();
        x = *it;
        H.erase(it);
        pop_heap(H.begin(),H.begin()+1,cmp());
        intrat[x] = 0;
        for(i=0;i<V[x].size();i++)
        {
            y = V[x][i];
            if(D[y]>D[x]+C[x][i])
            {
                D[y] = D[x] + C[x][i];
                if(!intrat[y])
                {
                    H.push_back(y);
                    intrat[y] = 1;
                    push_heap(H.end()-1,H.end(),cmp());
                }
            }
        }
    }
    for(i=2;i<=N;i++)
        if(D[i]==INF)
            out<<"0 ";
        else out<<D[i]<<' ';
    return 0;
}