#include<fstream>
#include<vector>
#include<queue>
using namespace std;

#define pb push_back

const int oo=1<<30;

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

struct muchie{int dest,cost;} d;

vector<muchie> V[50001];
queue<int> Q;
int D[50001];

int main()
{
    int i,N,M,a;
    in>>N>>M;
    for(i=1;i<=M;++i)
    {
        in>>a>>d.dest>>d.cost;
        V[a].pb(d);
    }

    for(i=1;i<=N;++i)
    {
        D[i]=oo;
    }
    D[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        a=Q.front();
        Q.pop();
        for(i=0;i<V[a].size();++i)
        {
            d=V[a][i];
            if(D[d.dest]>D[a]+d.cost)
            {
                D[d.dest]=D[a]+d.cost;
                Q.push(d.dest);
            }
        }
    }
    for(i=2;i<=N;++i)
    {
        if(D[i]!=oo)
        {
            out<<D[i]<<" ";
        }
        else
        {
            out<<"0 ";
        }
    }
    out<<'\n';
    in.close();
    out.close();
    return 0;
}