#include <fstream>
#include <vector>
#include <set>
 
#define NMAX 50010
#define infinite 100000000
#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) // Relaxam 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;
}