#include<fstream>
#include<queue>
#include<vector>
#define NMAX 50100
#define oo 99999
using namespace std;

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

vector< pair<int,int> > V[NMAX];
vector< pair<int,int> >::iterator it,sf;
int D[NMAX];
bool Uz[NMAX];
class cmp
{
    public:
    inline bool operator()(const int &x,const int &y){ return D[x]>D[y];}
};
priority_queue< int, vector<int> , cmp > H;
int main ()
{
    int N,M,x,y,c;
    in>>N>>M;
    while(M--)
    {
        in>>x>>y>>c;
        V[x].push_back(make_pair(y,c));
    }
    fill(D+2,D+N+1,oo);
    for( H.push(1) ; !H.empty() ; H.pop() )
    {
        x=H.top();
        Uz[x]=0;
        for(it=V[x].begin(),sf=V[x].end();it<sf;++it)
        {
            y=it->first,c=it->second;
            if(D[y]>D[x]+c)
            {
                D[y]=D[x]+c;
                if(Uz[y]==0)
                {
                    H.push(y);
                    Uz[y]=1;
                }
            }
        }
    }
    for(int i=2;i<=N;i++)
    out<<(D[i]<oo?D[i]:0)<<' ';
}