#include <fstream>
#include <vector>
#include <set>

#define NMAX 50000
#define infinite 1000000
#define mp make_pair
#define pb push_back

using namespace std;

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

int N,M, d[NMAX];
vector <int> G[NMAX], C[NMAX];
set <pair <int,int> > T;

void fullDijkstra()
{
    int val,x;
    
    for(int i=2; i<=N; ++i)
        d[i]=infinite;
    
    T.insert(mp(0,1));
    
    while(!T.empty())
    {
        val = (*T.begin()).first; // Min heap
        x = (*T.begin()).second;
        T.erase(T.begin());
        for(int i=0; i<G[x].size(); ++i) // Relaxăm nodul x
            if(d[G[x][i]]>d[x]+C[x][i])
                d[G[x][i]]=d[x]+C[x][i], T.insert(mp(d[G[x][i]],G[x][i]));
    }
}

int main()
{
    cin>>N>>M;
    
    int x,y,c;
    while(M--)
    {
        cin>>x>>y>>c;
        G[x].pb(y);
        C[x].pb(c);
    }
    fullDijkstra();
    for(int i=2; i<=N; ++i)
        cout<<(d[i] == infinite ? 0 : d[i])<<" ";
    
    return 0;
}